package newcoder;

import java.util.*;

/**
 * @Author 肖地洋
 * @Date 2022/6/20 10:10
 */


public class NC187 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param k int整型
     * @return int整型
     */
    public int compressString (String s, int k) {
        // write code here
        int n = s.length();
        int[][] dp = new int[n + 1][k + 1];
        for(int[] x:dp){
            Arrays.fill(x,n+1);
        }
        dp[0][0]=0;
//         dp数组的定义和初始化
        for (int i = 1; i <= n; i++) {
//             遍历每一个位置
            for (int j = 0; j <= i && j <= k; j++) {
//                 首先我们删除的元素，一定是要小于等于我们的当前的长度，并且小于我们题目中给定的可以最大删除的长度
                if (j < k) dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i - 1][j]);
//                 如果我们还可以继续删除，我们根据我们退出来的dp公式，这里怕数组越界所以我们统一把j -> j + 1
                int sameCharater = 0, differentCharater = 0;
//                 这个是寻找我们后面跟我们当前第i位字符有多少一样多少不一样，需要删除多少
                for (int m = i; m <= n; m++) {
//                     从当前位置向后遍历
                    if (s.charAt(m-1)==s.charAt(i-1)) sameCharater += 1;
                    else differentCharater += 1;
//                     判断两种情况进行增加的操作
                    if (j + differentCharater > k)
                        break;
//                     如果我们现在需要的删除次数加上我们已经删除的次数大于了我们总共的次数，我们直接不用继续向后判断了
                    dp[m][j + differentCharater] = Math.min(dp[m][j + differentCharater], len(sameCharater) + dp[i - 1][j]);
//                     否则的话，我们第m位删除了j + 不同的字符的次数，就是看我们当前这位和我们删除之后我们当前后面的长度加上原来的取一个最小值
                }
            }
        }
        return dp[n][k];
//         返回最后的答案
    }
    public int len(int n){
        if (n == 1) return 1;
        if (n < 10) return 2;
        if (n < 100) return 3;
        return 4;
    }

    public static void main(String[] args) {
        System.out.println(new NC187().compressString("abacad",2));

    }
}